#include <stdio.h>
#include <stdbool.h>

#define MaxSize 10 // 栈的最大容量

typedef struct
{
    int data[MaxSize]; // 静态数组存储栈元素
    int top;           // 栈顶指针
} SqStack;

// 1. 初始化栈
void InitStack(SqStack &S)
{
    S.top = -1; // 初始化栈顶指针为-1，表示空栈
}

// 2. 销毁栈（顺序栈无需特殊销毁操作）
void DestroyStack(SqStack &S)
{
    S.top = -1; // 重置栈顶指针即可
}

// 3. 压栈操作
bool Push(SqStack &S, int x)
{
    if (S.top >= MaxSize - 1)
    { // 栈满判断
        printf("Stack is full!\n");
        return false;
    }
    S.data[++S.top] = x; // 栈顶指针先+1，再放入元素
    return true;
}

// 4. 出栈操作
bool Pop(SqStack &S, int &x)
{
    if (S.top == -1)
    { // 栈空判断
        printf("Stack is empty!\n");
        return false;
    }
    x = S.data[S.top--]; // 先取出元素，栈顶指针再-1
    return true;
}

// 5. 获取栈顶元素
bool GetTop(SqStack S, int &x)
{
    if (S.top == -1)
    { // 栈空判断
        printf("Stack is empty!\n");
        return false;
    }
    x = S.data[S.top]; // 获取栈顶元素
    return true;
}

// 6. 获取栈底元素
bool GetBottom(SqStack S, int &x)
{
    if (S.top == -1)
    { // 栈空判断
        printf("Stack is empty!\n");
        return false;
    }
    x = S.data[0]; // 栈底元素是数组的第一个元素
    return true;
}

// 打印栈内容
void PrintStack(SqStack S)
{
    if (S.top == -1)
    {
        printf("Stack is empty\n");
        return;
    }

    printf("Stack [bottom->top]: ");
    for (int i = 0; i <= S.top; i++)
    {
        printf("%d ", S.data[i]);
    }
    printf("\n");
}

int main()
{
    SqStack S;
    InitStack(S); // 初始化栈

    // 压栈操作
    Push(S, 10);
    Push(S, 20);
    Push(S, 30);
    PrintStack(S); // Stack [bottom->top]: 10 20 30

    // 获取栈顶和栈底
    int top, bottom;
    GetTop(S, top);
    GetBottom(S, bottom);
    printf("Top: %d, Bottom: %d\n", top, bottom); // Top: 30, Bottom: 10

    // 出栈操作
    int popped;
    Pop(S, popped);
    printf("Popped: %d\n", popped); // Popped: 30
    PrintStack(S);                  // Stack [bottom->top]: 10 20

    // 栈满测试
    printf("Testing stack full:\n");
    for (int i = 0; i < MaxSize + 2; i++)
    {
        if (!Push(S, i))
            break;
    }

    // 栈空测试
    printf("Testing stack empty:\n");
    while (Pop(S, popped))
    {
        printf("Popped: %d\n", popped);
    }

    // 获取空栈元素测试
    GetTop(S, top);
    GetBottom(S, bottom);

    DestroyStack(S); // 销毁栈
    return 0;
}